class TFNP

Definition

Define the complexity class, TFNP (total functions from NP), as all total search problems in FNP.

Notes

• could also be called $\mathrm{F}(\mathrm{NP} \cap \mathrm{coNP})$

References

1. N. Megiddo and C. H. Papadimitriou, “On total functions, existence theorems and computational complexity,” Theoretical Computer Science, vol. 81, no. 2, pp. 317–324, Apr. 1991, doi: 10.1016/0304-3975(91)90200-L.
2. N. Bitansky et al., “PPAD is as hard as LWE and iterated squaring,” 2022, Cryptology ePrint Archive: cryptoeprint:2022/1272. [Online]. Available: https://eprint.iacr.org/2022/1272
3. https://en.wikipedia.org/wiki/TFNP